Copending Application Ser. No. 717,341, filed Aug. 24, 1976 in the name of the present inventor, describes and claims an asynchronous time division statistical multiplexing system for computer communications, in which user messages are transmitted from individual terminals to a central processor in random order. The messages are statistically multiplexed in each multiplexer/demultiplexer station, with time slots being provided in the communication channel as each message is received from the various terminals and with no time slots being assigned for idle periods, which greatly increases channel utilization. To improve channel efficiency, several characters from the same terminal are collected together to form data sub-blocks so as to reduce address label requirements. The data sub-blocks are grouped into data blocks for transmission over the communication channel; each data block having a block identification number, destination number, an error checking code and a synchronization character. A demultiplexer is provided in the multiplexer/demultiplexer station for receiving the data blocks from a distant station, for sending positive and negative acknowledgment messages to the distant station, for demultiplexing the received data blocks and for distributing the demultiplexed data blocks to the various terminals.
The prior art synchronous time division multiplexing computer communication systems are inefficient insofar as optimization of channel use is concerned. For that reason, more flexible systems, namely asynchronous time division multiplexing have been introduced in the prior art, and such systems provide a user with access to the common communication channel only when he has a message to transmit. In the asynchronous time division multiplexing system, no channel bandwidth is assigned to the idle terminals. Since the multiplexed messages transmitted over the common communication channel in the asynchronous system are in a random order, such multiplexing is also known as statistical multiplexing. The system of the copending application, and the system of the present invention, both are predicated on the statistical multiplexing concept.
Statistical multiplexing involves a certain amount of complexity because every message transmitted over the common communication channel must be accompanied by a label which identifies the terminal from which it originated, and because buffering is required to handle the random message arrivals. It has been shown, however, that this complexity is more than offset by the statistical systems message handling ability, and by its high average communication channel utilization.
In the asynchronous time division multiplexing system of the copending application, and of the present invention, user messages are labelled by addresses and are statistically multiplexed for transmission over a common communication channel to a central processor. A multiplicity of individual terminals are connected to a multiplexer in a multiplexer/demultiplexer station, and messages received by the station from the individual terminals are multiplexed on an asynchronous time division basis for transmission over one or more common communication channels to one or more central processors, or to one or more multiplexer/demultiplexer stations.
Each message, or character, from the individual input terminals is parity checked at the input interface to the multiplexer. All characters received correctly from the individual input terminals are echoed back to the operators, by a local echo function. If a character is not correctly received, as detected by a parity bit error, that character is not echoed back, and the operator is thereby informed that he must retype the character. In the asynchronous time division multiplexing system of the copending application, and of the present invention, as mentioned above, time slots are assigned in the communication channel for each character received by the multiplexer in the multiplexer/demultiplexer station, but no time slots are assigned for the idle terminal. This greatly increases channel utilization in the common communication channel. To handle traffic at the statistical peak, a two-stage buffer is included in the multiplexer. The first stage of the buffer consists of a first-in-first-out (FIFO) memory, and the second stage consists of a read/write (R/W) memory.
The FIFO serves to collect the randomly received characters from all the input terminals, each character including a start bit, a stop bit, and parity bit. These bits are removed before the characters are fed into the FIFO, and an address label is added to each character which identifies the terminal from which the character was received. The contents of the FIFO are then fed to the second stage of the buffer which is the R/W memory, in which they are formed into a data block for transmission. To improve channel efficiency, several characters from the same terminal are collected together in the R/W memory to form a data sub-block, with all the characters in the data sub-block being identified by a single address label, so as to reduce the address label requirements in the overall system.
The multiplexer/demultiplexer station in the system described in the copending application includes a microprocessor which controls the flow of signals through the station. The multiplexer also includes a block time-out circuit which serves to notify the microprocessor when a prescribed block time-out interval has elapsed since a first character was received from the R/W memory to form a data sub-block. When a block time-out interval occurs, as indicated by a counter in the block time-out circuit, all the data sub-blocks which contain at least one data character are chained together to form a data block for transmission to the central processor over the common communication channel. The block time-out circuit prevents excessive response time delays. When a data block is filled up to its maximum length, the block is immediately transmitted over the common communication line by the microprocessor without any intercession from the block time-out circuit.
In the system of the copending application, and of the present invention, a demultiplexer is also provided in the multiplexer/demultiplexer station, and it is coupled to the individual terminals, so that messages for the individual output terminals received from the central processor over the common communication channel in an asynchronous time division multiplexed format may be demultiplexed and directed to the output terminals identified by the individual messages. In the system described in the copending application, a single microprocessor controls the signal flow through the multiplexer from the input terminals, and through the demultiplexer in the multiplexer/demultiplexer station to the output terminals.
In the statistical multiplexing system of the present invention, on the other hand, two microprocessors are included in the multiplexing/demultiplexing station, each being provided with independent local memories. The two microprocessors will be designated herein as the "send microprocessor" and the "receive microprocessor". Specifically, in the statistical multiplexing system of the copending application, a single microprocessor is used for processing many of the message handling tasks such as grouping arrival characters from a given input terminal into addressed data sub-blocks, multiplexing the data sub-blocks into data blocks for transmission, handling of block time-outs and acknowledgment time-outs, error control interrupts, issuing acknowledgment messages, demultiplexing of received multiplexed data blocks from the central processor to their designated output terminals, handling dynamic buffer management, self and remote diagnostics, and so on. The aforesaid functions all operate in real time and, therefore, the processing speed of the microprocessor is an important factor and influences the performance of the statistical multiplexing system.
Because of the limited capability and low cost of the present-day microprocessor, the system of the present invention includes two microprocessors for the aforesaid message handling tasks. Although a dual-processor system provides more computing capabilities, it does create a complexity problem in information control, particularly in the inter-process communication between the two microprocessors. It is evident that excessive inter-process communication could greatly reduce the efficiency and operational speed of the system.
In the system of the present invention, the message handling from the input terminals to the multiplexer output is processed by one of the two microprocessors, designated the "send microprocessor", and the handling of the received multiplexed input data blocks and the demultiplexing of the blocks and the distribution thereof to the designated output terminals is carried out by the second microprocessor, designated the "received microprocessor". Since the send and receive tasks are generally independent of one another, very litte communication is required between the two microprocessors, so that there is no material increase in system complexity. Furthermore, each microprocessor in the system to be described has its independent local memory for storing resident programs and for buffering, which also reduces the need for intermicroprocessor communication.
The bi-directional inter-process communication between the two microprocessors in the system of the invention is handled in the embodiment to be described by a temporary storage in the form of a first-in-first-out (FIFO) buffer facility. Such task partitioning results in minimum inter-process communications, and reduces the complexity of the system. With the extra processing capabilities, the statistical multiplexing system of the present invention is capable of self and remote diagnostic and statistic monitoring, as well as traffic flow control to prevent congestion, all of which are important to the efficient operation of the statistical multiplexing system.